// 若top前k人得分都>=k，且其他人的得分都<=k，则该小组得分为k。
// [5, 2, 7, 11, 8, 6, 5, 1]，top 5为11, 8, 7, 6, 5，其他为5, 2, 1，所以得分为5。
// 计数排序O(N)
int getAns(vector<int>& nums) {
    vector<int> rec(nums.size());
    for (auto& n: nums) {
        if (n < nums.size()) rec[n]++;
    }
    int cnt = 0;
    for (int i = nums.size() - 1; i >= 0; --i) {
        cnt += rec[i]; //得分大于等于i的个数
        if (cnt >= nums.size() - i + 1) { //保证得分最高的前k个人的得分都b不低于i
            return i;
        }
    }
    return -1;
}

// 法二：partition O(N)
int getAns(vector<int>& nums, int start, int end) {
    int low = start;
    int high = end;
    int mid = (high - low) / 2 + low;
    int p = nums[mid];
    while (low < high) {
        while (nums[low] < p) low++;
        while (nums[high] > p) high--;
        if (low <= high) {
            swap(nums[low++], nums[high--]);
        }
    }
    // p的当前下标，可能是low，high或者(low + high) / 2
    int rec;
    if (nums[low] == p) rec = low;
    else if (nums[high] == p) rec = high;
    else rec = (high - low) / 2 + low;
    
    if (nums.size() - rec == p) return p;
    else if (nums.size() - rec > p) return getAns(nums, rec, end);
    else return getAns(nums, start, rec);
}

int main() {
    vector<int> input = {5, 2, 7, 11, 8, 6, 5, 1};
//    cout << getAns(input, 0, input.size() - 1);
    cout << getAns(input);
    return 0;
}